#include <vector>
using namespace std;
// Definition for singly-linked list.
struct ListNode
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

// 变种归并排序
class Solution
{
public:
    ListNode *marge(ListNode *left, ListNode *right)
    {
        ListNode *temp_head = new ListNode(0, left);
        ListNode *cur = temp_head;
        while (left || right)
        {
            if (!right || left && left->val < right->val)
            {
                cur->next = left;
                left = left->next;
            }
            else
            {
                cur->next = right;
                right = right->next;
            }
            cur = cur->next;
        }
        cur->next = nullptr;
        return temp_head->next;
    }
    ListNode *mergeKLists(vector<ListNode *> &lists)
    {
        if (!lists.size())
            return nullptr;
        int step = 1;
        for (int step = 1; step < lists.size() + 1 / 2; step *= 2)
        {
            for (int cur = 0; cur < lists.size(); cur += 2 * step)
            {
                ListNode *left = lists[cur];
                ListNode *right = cur + step >= lists.size() ? nullptr : lists[cur + step];
                lists[cur] = marge(left, right);
            }
        }
        return lists[0];
    }
};